|
|
Abstraction in Automata Algorithms
Kocourek, Tomáš ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
Tato práce si klade za cíl implementaci a experimentální porovnání protiřetězcových algoritmů s abstrakcí a bez abstrakce, které testují prázdnost alternujících automatů. Autor také navrhuje vlastní algoritmy s abstrakcí a navrhuje několik optimalizací pro existující abstraktní algoritmy. Práce popisuje teoretické pozadí studovaných algoritmů a navrhuje efektivní způsob implementace datových struktur, které jsou těmito algoritmy používány. Experimentální vyhodnocení na náhodných automatech ukazuje, že algoritmy bez abstrakce vykazují obecně lepší výsledky, neboť nevyužívají náročné operace průniku a komplementace shora a zdola uzavřených množin. V případě automatů s vysokou hustotou přechodů však algoritmy bez abstrakce zpomalují a algoritmy s abstrakcí naopak zrychlují.
|
|
|
Improving Precision of Program Analysis in the 2LS Framework
Smutný, Martin ; Vojnar, Tomáš (referee) ; Malík, Viktor (advisor)
Cílem této práce je navrhnout způsob vedoucí ke zvýšení přesnosti analýzy programů pomocí nástroje 2LS, založený na existujících konceptech, a to hlavně na syntézi invariant na základě šablon. 2LS je nástroj pro statickou analýzu programů napsaných v jazyce C, který využívá SMT solver a abstraktní interpretaci k automatickému odvození invariant. V případě kdy 2LS nedokáže rozhodnout zda je program správný, navrhované řešení analyzuje invarianty vypočítané v různých abstraktních doménách, a identifikuje takové části invariant, které mohou s největší pravděpodobností způsobit nejednoznačnost verifikace. Pomocí těchto získaných informací, dokáže navrhnutá metoda identifikovat proměnné původního programu, na kterých pravděpodobně závisí úspěch verifikace. Výstup tohoto řešení může posloužit jako zpětná vazba indikující proměnné, jejíchž problematické hodnoty by měly být omezeny. Také může být výstup využit vývojáři 2LS pro účely debugování při vývoji nových analýz. Řešení bylo implementováno v nástroji 2LS. Na základě různých experimentů mezinárodní soutěže ve verifikaci programů SV-COMP, dokáže řešení identifikovat proměnné způsobující nejednoznačnost verifikace ve více než polovině programů, na kterých verifikace momentálně selhává.
|
|
|
Abstraction in Automata Algorithms
Kocourek, Tomáš ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
Tato práce si klade za cíl implementaci a experimentální porovnání protiřetězcových algoritmů s abstrakcí a bez abstrakce, které testují prázdnost alternujících automatů. Autor také navrhuje vlastní algoritmy s abstrakcí a navrhuje několik optimalizací pro existující abstraktní algoritmy. Práce popisuje teoretické pozadí studovaných algoritmů a navrhuje efektivní způsob implementace datových struktur, které jsou těmito algoritmy používány. Experimentální vyhodnocení na náhodných automatech ukazuje, že algoritmy bez abstrakce vykazují obecně lepší výsledky, neboť nevyužívají náročné operace průniku a komplementace shora a zdola uzavřených množin. V případě automatů s vysokou hustotou přechodů však algoritmy bez abstrakce zpomalují a algoritmy s abstrakcí naopak zrychlují.
|
|
|
Improving Precision of Program Analysis in the 2LS Framework
Smutný, Martin ; Vojnar, Tomáš (referee) ; Malík, Viktor (advisor)
Cílem této práce je navrhnout způsob vedoucí ke zvýšení přesnosti analýzy programů pomocí nástroje 2LS, založený na existujících konceptech, a to hlavně na syntézi invariant na základě šablon. 2LS je nástroj pro statickou analýzu programů napsaných v jazyce C, který využívá SMT solver a abstraktní interpretaci k automatickému odvození invariant. V případě kdy 2LS nedokáže rozhodnout zda je program správný, navrhované řešení analyzuje invarianty vypočítané v různých abstraktních doménách, a identifikuje takové části invariant, které mohou s největší pravděpodobností způsobit nejednoznačnost verifikace. Pomocí těchto získaných informací, dokáže navrhnutá metoda identifikovat proměnné původního programu, na kterých pravděpodobně závisí úspěch verifikace. Výstup tohoto řešení může posloužit jako zpětná vazba indikující proměnné, jejíchž problematické hodnoty by měly být omezeny. Také může být výstup využit vývojáři 2LS pro účely debugování při vývoji nových analýz. Řešení bylo implementováno v nástroji 2LS. Na základě různých experimentů mezinárodní soutěže ve verifikaci programů SV-COMP, dokáže řešení identifikovat proměnné způsobující nejednoznačnost verifikace ve více než polovině programů, na kterých verifikace momentálně selhává.
|
guest ::
